interface LikeRect {
    x: number,
    y: number,
    width: number,
    height: number,
    halfWidth?: number,
    halfHeight?: number,
}

interface LikeCollider {
    x: number,
    y: number,
    width: number,
    height: number,
}
let color = [
    cc.Color.BLACK,
    cc.Color.RED,
    cc.Color.BLUE,
    cc.Color.ORANGE,
    cc.Color.GREEN,
]

let catchTree = [];
export class QuadTree<T extends LikeCollider> {
    //subnodes
    protected nodes: QuadTree<T>[] = null;
    //children contained directly in the node
    protected children: T[] = null;
    private _bounds: LikeRect = null;

    //read only
    protected _depth = 0;
    protected _maxChildren = 6;
    protected _maxDepth = 6;

    public constructor(bounds: LikeRect, depth: number, maxDepth: number, maxChildren: number) {
        this._bounds = bounds;
        this.children = [];
        this.nodes = [];
        this._maxChildren = maxChildren || 10;
        this._maxDepth = maxDepth || 4;
        this._depth = depth || 0;
        if (!this._bounds.halfHeight) this._bounds.halfHeight = this._bounds.height / 2;
        if (!this._bounds.halfWidth) this._bounds.halfWidth = this._bounds.width / 2;
    }

    public getAllNeedTestColliders(out: T[][]) {
        if (this.children.length)
            out.push(this.children);
        for (let i = 0, len = this.nodes.length; i < len; i++) {
            let node = this.nodes[i];
            node.getAllNeedTestColliders(out);
        }
    }

    public render(pen: cc.Graphics) {
        for (let i = 0, len = this.nodes.length; i < len; i++) {
            let node = this.nodes[i];
            node && node.render(pen);
        }
        pen.lineWidth = cc.misc.clampf(8 - this._depth, 2, 8);
        pen.strokeColor = color[this._depth];
        pen.moveTo(this._bounds.x, this._bounds.y);
        pen.lineTo(this._bounds.x + this._bounds.width, this._bounds.y);
        pen.lineTo(this._bounds.x + this._bounds.width, this._bounds.y + this._bounds.height);
        pen.lineTo(this._bounds.x, this._bounds.y + this._bounds.height);
        pen.close();
        pen.stroke();
    }

    public insert(item) {
        if (this.nodes.length) {
            let indexes = this._findIndexs(item);
            for (let i = 0, len = indexes.length; i < len; i++) {
                this.nodes[indexes[i]].insert(item);
            }
            return;
        }
        this.children.push(item);
        let len = this.children.length;
        if (this._depth < this._maxDepth && len > this._maxChildren /*&& (item.width < this._bounds.halfWidth && item.height < this._bounds.halfHeight)*/) {
            if (!this.nodes.length)
                this.subdivide();
            for (let i = 0; i < len; i++) {
                let indexes = this._findIndexs(this.children[i]);
                for (let k = 0, klen = indexes.length; k < klen; k++) {
                    this.nodes[indexes[k]].insert(this.children[i]);
                }
            }
            this.children.length = 0;
        }
    }

    public retrieve(item: T, out: T[]) {
        let indexes = this._findIndexs(item);
        if (this.children.length)
            out.push.apply(out, this.children);
        if (this.nodes.length) {
            for (let i = 0, len = indexes.length; i < len; i++) {
                this.nodes[indexes[i]].retrieve(item, out);
            }
        }
        out = out.filter((item, index) => {
            return out.indexOf(item) >= index;
        });
    }

    /**
     *查找当前碰撞体在那几个象限
     *
     * ---------
     * | 0 | 3 |
     * ----|----
     * | 1 | 2 |
     * ---------
     *
     * @param {T} item
     * @return {*} 
     * @memberof QuadTree
     */
    public _findIndexs(pRect: T) {
        let b = this._bounds;
        //象限中点
        let verticalMidpoint = b.x + b.halfWidth;
        let horizontalMidpoint = b.y + b.halfHeight;
        let bottom = pRect.y < horizontalMidpoint,
            left = pRect.x < verticalMidpoint,
            right = pRect.x + pRect.width > verticalMidpoint,
            top = pRect.y + pRect.height > horizontalMidpoint;
        let indexes = [];
        //top-left quad
        if (top && left) {
            indexes.push(0);
        }

        //bottom-left quad
        if (bottom && left) {
            indexes.push(1);
        }

        //bottom-right quad
        if (bottom && right) {
            indexes.push(2);
        }

        //top-right quad
        if (top && right) {
            indexes.push(3);
        }
        return indexes;
    }

    /**
     * ---------
     * | 0 | 3 |
     * ----|----
     * | 1 | 2 |
     * ---------
     */
    public subdivide() {
        let nextLevel = this._depth + 1,
            subWidth = this._bounds.halfWidth,
            subHeight = this._bounds.halfHeight,
            x = this._bounds.x,
            y = this._bounds.y;
        //top left node
        this.nodes[0] = new QuadTree({
            x: x,
            y: y + subHeight,
            width: subWidth,
            height: subHeight
        }, nextLevel, this._maxDepth, this._maxChildren);

        //bottom left node
        this.nodes[1] = new QuadTree({
            x: x,
            y: y,
            width: subWidth,
            height: subHeight
        }, nextLevel, this._maxDepth, this._maxChildren);

        //bottom right node
        this.nodes[2] = new QuadTree({
            x: x + subWidth,
            y: y,
            width: subWidth,
            height: subHeight
        }, nextLevel, this._maxDepth, this._maxChildren);

        //top right node
        this.nodes[3] = new QuadTree({
            x: x + subWidth,
            y: y + subHeight,
            width: subWidth,
            height: subHeight
        }, nextLevel, this._maxDepth, this._maxChildren);
    }

    public clear() {
        this.children.length = 0;
        for (let i = 0, len = this.nodes.length; i < len; i++) {
            this.nodes[i].clear();
        }
        this.nodes.length = 0;
    }
}
